/*
题目: 最大为 N 的数字组合
给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = ['1','3','5']，我们可以写数字，如 '13', '551', 和 '1351315'。

返回 可以生成的小于或等于给定整数 n 的正整数的个数 。

https://leetcode.cn/problems/numbers-at-most-n-given-digit-set
 */
public class AtMostNGivenDigitSet {
    int[] choices = null;
    int len = 0;

    int[] memo = null;
    char[] cs = null;
    int size = 0;

    public int atMostNGivenDigitSet(String[] digits, int n) {
        len = digits.length;
        choices = new int[len];
        for (int i = 0; i < len; i ++)
            choices[i] = Integer.valueOf(digits[i]);

        cs = String.valueOf(n).toCharArray();
        size = cs.length;

        // 由于这个题只要求 <= n , 这个条件我们是可以直接排除掉的, 也没有什么其他要求, 所以一维就足够
        memo = new int[size];
        Arrays.fill(memo, -1);

        return dfs(0, true, false);
    }

    private int dfs(int pos, boolean limited, boolean hasNum) {
        if (pos >= size) {
            return hasNum ? 1 : 0;
        }

        // 必须要 hasNum 的条件下才能取记忆化的结果
        // 5  3  2
        // 0  5  2  如上 在 memo[0] 的情况下 0 开头的数字根本就不是一个有效数字, 所以不能直接使用这里的结果
        if (!limited && hasNum &&  memo[pos] != -1) {
            return memo[pos];
        }

        int src = 0;
        if (!hasNum) {
            src += dfs(pos + 1, false, false);
        }

        int up = limited ? cs[pos] - '0' : 9;
        for (int d : choices) {
            if (d > up)
                break ;

            src += dfs(pos + 1, limited && d == up, true);
        }

        // 不受限 并且 记忆化 才赋值
        if (!limited && hasNum) {
            memo[pos] = src;
        }
        return src;
    }
}
